package org.algorithm.熊猫.字符串;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * @date 2022-04-15 星期五 00:00
 * 给定两个字符串s和 p，找到s中所有p的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
 * <p>
 * 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
 * <p>
 * <p>
 * <p>
 * 示例1:
 * <p>
 * 输入: s = "cbaebabacd", p = "abc"
 * 输出: [0,6]
 * 解释:
 * 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
 * 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
 * 示例 2:
 * <p>
 * 输入: s = "abab", p = "ab"
 * 输出: [0,1,2]
 * 解释:
 * 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
 * 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
 * 起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class 找到字符串中所有字母异位词 {

    @Test
    public void test(){
        System.out.println(findAnagrams("baa","aa"));
    }

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();

        int pL = p.length();
        int sL = s.length();
        if(sL<pL){
            return result;
        }

        int[] sCount = new int[26];
        int[] pCount = new int[26];
        for (int i = 0; i < pL; ++i) {
            ++sCount[s.charAt(i) - 'a'];
            ++pCount[p.charAt(i) - 'a'];
        }
        if (Arrays.equals(sCount, pCount)) {
            result.add(0);
        }


        for (int i = 0; i < sL - pL; i++) {
            --sCount[s.charAt(i) - 'a'];
            ++sCount[s.charAt(i + pL) - 'a'];

            if (Arrays.equals(sCount, pCount)) {
                result.add(i + 1);
            }
        }

        return result;
    }

    private boolean court(String s, int start, int end, HashMap<Character, Integer> clone) {
        for (int i = start; i <= end; i++) {
            Integer orDefault = clone.getOrDefault(s.charAt(i), 0);
            if (orDefault == 0) {
                return false;
            }
            orDefault--;
            if (orDefault == 0) {
                clone.remove(s.charAt(i));
            }else {
                clone.put(s.charAt(i),orDefault);
            }
        }
        return clone.isEmpty();
    }
}
